/* 
 * File:   MultipleTree.h
 * Author: johnneyshi
 *
 * Created on 2013年3月21日, 上午8:50
 */

#ifndef MULTIPLETREE_H
#define	MULTIPLETREE_H
#include "MultipleTreeNode.h"
#include "JSerialize.h"
#include <iostream>
using namespace std;


namespace mylib
{
    enum FindFlag
    {
        FindNode,
        FindAncestorNode,
        //FindParentNode,
        NoPlace,
        EmptyTree
    };
    template <class KeyType,class DataType>
    class MultipleTree : public JSerialize
    {
    public:
        void (*AddNodeSuccessHandler)(MultipleTreeNode<KeyType,DataType>* pNode);
        MultipleTreeNode<KeyType,DataType>* root;
        MultipleTree(IMultipleTreeNodeCompare<KeyType>& _compare) : compare(_compare), root(NULL)
        {
            AddNodeSuccessHandler = NULL;
        }
        MultipleTree()
        {
            AddNodeSuccessHandler = NULL;
        }
        
        IMultipleTreeNodeCompare<KeyType>& compare;
        /*
         * 传入的_startNode
         */
        MultipleTreeNode<KeyType,DataType>* Add(const KeyType& _key,const DataType& _data,MultipleTreeNode<KeyType,DataType>* _startNode = NULL)
        {
            if(_startNode == NULL)
            {
                _startNode = this->root;
            }
            std::pair<FindFlag,MultipleTreeNode<KeyType,DataType>* > flag = FindRealPlace(_key,_startNode);
            switch(flag.first)
            {
                case FindNode:
                    return flag.second;
                case FindAncestorNode:
                    return AutoAddChildNode(_key,_data,flag.second);
                case NoPlace:
                    return NULL;
                case EmptyTree:
                    return SetRootNode(_key,_data);
                default:
                    return NULL;
            }
        }
        void Print()
        {
            PrintIte(this->root);
        }
        //找到真是的位置，如果有，返回；如果没有，返回需要插入的位置
        std::pair<FindFlag,MultipleTreeNode<KeyType,DataType>* > FindRealPlace(const KeyType& _key,MultipleTreeNode<KeyType,DataType>* _startNode = NULL)
        {
            if(root == NULL)
            {
                return std::make_pair<FindFlag,MultipleTreeNode<KeyType,DataType>*>(EmptyTree,root);
            }
            if(_startNode == NULL)
            {
                _startNode = root;
            }
            return FindRealPlaceItera(_key,_startNode);
        }
        /*序列化成这样的形式A(B()C(E()F())D(G()H()))(I(J()K()))
        //往下一层加"("，往上一层加")"，因为本书中是序列化的，为了和节点数据分开，因为节点数据的大小肯定不会小于0
        //那么就往下一层，加"-1",往上一层加"-2";
        //在序列化和反序列化时，根节点一定不能位空
        */
        int Serialize(JInOutPut& strea,int& allSize)
        {
            int selfSize = 0,classSize = 0;
            JSerialize::SerializeHead(strea,selfSize,classSize);
            SerializeIte(strea,classSize,this->root);
            JSerialize::SerializeTail(strea,allSize,selfSize,classSize);
        }
        
	int ReSerialize(JInOutPut& strea)
        {
            MultipleTreeNode<KeyType,DataType>* pCurrentNode = NULL,*pParentNode = NULL;
            int classSize;
            classSize = JSerialize::ReSerializeHead(strea);
            int restSize = classSize;
            while(restSize > 0)
            {
                int flag = GetUpDownOrAdd(strea);
                switch(flag)
                {
                    //向下
                    case -1:
                        pParentNode = pCurrentNode;
                        pCurrentNode = NULL;
                        restSize -= sizeof(int);
                        break;
                    //向上
                    case -2:
                        pParentNode = pParentNode->pParent;
                        pCurrentNode = NULL;
                        restSize -= sizeof(int);
                        break;
                    case 0:
                        MultipleTreeNode<KeyType,DataType>* pNode = new MultipleTreeNode<KeyType,DataType>();
                        int classSize1 = pNode->ReSerialize(strea);
                        if(pParentNode == NULL)
                        {
                            this->root = pNode;
                        }
                        else if(pCurrentNode == NULL)
                        {
                            pNode->pParent = pParentNode;
                            pParentNode->pChildNodes.push_back(pNode);
                        }
                        pCurrentNode = pNode;
                        restSize -= (classSize1 + sizeof(int));
                        break;
                }
            }
            return classSize;
            //ReSerializeIte(strea,NULL,NULL);
        }
    private:
        int SerializeIte(JInOutPut& strea,int& allSize,MultipleTreeNode<KeyType,DataType>* pNode)
        {
            pNode->Serialize(strea,allSize);
            //写入“-1”
            JSerialize::PutInt(strea,-1,allSize);
            typename std::list<MultipleTreeNode<KeyType,DataType>*>::iterator ite = pNode->pChildNodes.begin();
            for(;ite != pNode->pChildNodes.end(); ++ite)
            {
                SerializeIte(strea,allSize,*ite);
            }
            //写入“-2”
            JSerialize::PutInt(strea,-2,allSize);
        }
        void ReSerializeIte(JInOutPut& strea,MultipleTreeNode<KeyType,DataType>* pParentNode,MultipleTreeNode<KeyType,DataType>* pCurrentNode)
        {
            //这是根节点，还没有被赋值
            if(pParentNode == NULL)
            {
                MultipleTreeNode<KeyType,DataType>* pNode = new MultipleTreeNode<KeyType,DataType>*();
                pNode->ReSerialize(strea);
                this->root = pNode;
                //读取到下一层，使得pParentNode为父节点
                int flag = GetUpDownOrAdd(strea);
                ReSerializeIte(strea,this->root,NULL);
                flag = GetUpDownOrAdd(strea);
            }
            else
            {
                //MultipleTreeNode<KeyType,DataType>* pNode
                //读取前面的一个int，看是否是-1或者-2，来决定是不是需要下一层或者上一层
                int flag = GetUpDownOrAdd(strea);
                switch(flag)
                {
                    //向下一层
                    case -1:
                        ReSerializeIte(strea,pCurrentNode,NULL);
                        break;
                    //向上一层
                    case -2:
                        ReSerializeIte(strea,pParentNode->pParent,NULL);
                        break;
                    //同一层添加节点
                    case 0:
                        MultipleTreeNode<KeyType,DataType>* pNode = new MultipleTreeNode<KeyType,DataType>*();
                        pNode->ReSerialize(strea);
                        pNode->pParent = pParentNode;
                        pParentNode->pChildNodes.push_back(pNode);
                        ReSerializeIte(strea,pParentNode,pNode);
                        break;
                    default:
                        break;
                }
            }
        }
        
        /*得到标志
         * -1代表下一层，-2代表上一层，0代表添加节点
         */
        int GetUpDownOrAdd(JInOutPut& strea)
        {
            int flag = JSerialize::GetInt(strea,sizeof(int));
            if(flag == -1 || flag == -2)
            {
                return flag;
            }
            //这时候需要把读取指针直向之前sizeof(int)的大小
            strea.SeekP(-1 * sizeof(int),PutPositionCur);
            return 0;
        }
        void PrintIte(MultipleTreeNode<KeyType,DataType>* pNode)
        {
            cout << "key:" << pNode->key << endl;
            cout << "data:" << endl;
            cout << pNode->data << endl;
            cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" << endl;
            typename std::list<MultipleTreeNode<KeyType,DataType>*>::iterator ite = pNode->pChildNodes.begin();
            for(;ite != pNode->pChildNodes.end(); ++ite)
            {
                PrintIte((*ite));
            }
        }
        MultipleTreeNode<KeyType,DataType>* SetRootNode(const KeyType& _key,const DataType& _data)
        {
            this->root = new MultipleTreeNode<KeyType,DataType>(_key,_data,NULL);
            return this->root;
        }
        //自动添加子节点：比如要插入的这个节点，只能找到他的祖先，没有父节点，那么自动插入父节点
        MultipleTreeNode<KeyType,DataType>* AutoAddChildNode(const KeyType& _key,const DataType& _data,MultipleTreeNode<KeyType,DataType>* _ancestorNode)
        {
            std::list<KeyType> keys = compare.GenerateAncestor(_key);
            keys.push_back(_key);
            typename std::list<KeyType>::iterator ite = keys.begin();
            MultipleTreeNode<KeyType,DataType>* pParentNode = _ancestorNode;
            for(;ite != keys.end(); ++ite)
            {
                if(compare.IsAncestor(*ite,_ancestorNode->key) || compare.Compare(*ite,_ancestorNode->key) == 0)
                {
                    continue;
                }
                else
                {
                    pParentNode = AddChild(*ite,_data,pParentNode);
                }
            }
            return pParentNode;
        }
        //返回添加的节点的指针
        MultipleTreeNode<KeyType,DataType>* AddChild(const KeyType& _key,const DataType& _data,MultipleTreeNode<KeyType,DataType>* _pParentNode)
        {
            typename std::list<MultipleTreeNode<KeyType,DataType>*>::iterator ite = _pParentNode->pChildNodes.begin();
            typename std::list<MultipleTreeNode<KeyType,DataType>*>::iterator iteEnd = _pParentNode->pChildNodes.end();
            for(;ite != iteEnd; ++ite)
            {
                int result = compare.Compare((*ite)->GetKey(),_key);///////////////////////////
                if(result == 0)
                {
                    return *ite;
                }
                else if(result < 0)
                {
                    continue;
                }
                //现在这个节点是第一个比他大的节点
                else
                {
                    MultipleTreeNode<KeyType,DataType>* pNode = new MultipleTreeNode<KeyType,DataType>(_key,_data,_pParentNode);
                    _pParentNode->pChildNodes.insert(ite,pNode);
                    if(AddNodeSuccessHandler != NULL)
                    {
                        AddNodeSuccessHandler(pNode);
                    }
                    return pNode;
//                    //插入到最前面
//                    if(ite == _pParentNode->pChildNodes.begin())
//                    {
//                        _pParentNode->pChildNodes.push_front(pNode);
//                    }
//                    //插入到这个节点的前面
//                    else
//                    {
//                        --ite;
//                        _pParentNode->pChildNodes.
//                    }
                    break;
                }
            }
            //最后一个元素也要比插入的元素小，那么插入到最后
            if(ite == iteEnd)
            {
                MultipleTreeNode<KeyType,DataType>* pNode = new MultipleTreeNode<KeyType,DataType>(_key,_data,_pParentNode);
                _pParentNode->pChildNodes.push_back(pNode);
                if(AddNodeSuccessHandler != NULL)
                {
                    AddNodeSuccessHandler(pNode);
                }
                return pNode;
            }
            return NULL;
        }

        //传进来的_startNode不能为NULL
        std::pair<FindFlag,MultipleTreeNode<KeyType,DataType>*> FindRealPlaceItera(const KeyType& _key,MultipleTreeNode<KeyType,DataType>* _startNode)
        {
            if(compare.Compare(_startNode->key,_key) == 0)
            {
                return std::make_pair<FindFlag,MultipleTreeNode<KeyType,DataType>*>(FindNode,_startNode);
            }
            else if(compare.IsAncestor(_startNode->key,_key))
            {
                typename std::list<MultipleTreeNode<KeyType,DataType>*>::iterator ite = _startNode->pChildNodes.begin();
                for(;ite != _startNode->pChildNodes.end(); ++ite)
                {
                    std::pair<FindFlag,MultipleTreeNode<KeyType,DataType>*> flag = FindRealPlaceItera(_key,*ite);
                    switch(flag.first)
                    {
                        case FindNode:
                            return flag;
                        case FindAncestorNode:
                            return flag;
                        case NoPlace:
                            break;
                        case EmptyTree:
                            return flag;
                        default:
                            break;
                    }
                }
                //如果所有的兄弟都不相等或者其祖先，但是它的上一个节点是其祖先，那么就说明需要插入兄弟节点
                return std::make_pair<FindFlag,MultipleTreeNode<KeyType,DataType>*>(FindAncestorNode,_startNode);
            }
            else
            {
                return std::make_pair<FindFlag,MultipleTreeNode<KeyType,DataType>*>(NoPlace,NULL);
            }
        }
    };
}
#endif	/* MULTIPLETREE_H */

